11338 - Minefield/11338.AC.clean.cpp

   1 #include <iostream>
   2 #include <vector>
   3 #include <queue>
   4 #include <map>
   5 #include <cmath>
   6 #include <sstream>
   7 #include <functional>
   8
   9 using namespace std;
  10
  11 const double infinity = 1E20;
  12
  13 struct point{
  14   double x, y;
  15   point(double X, double Y){ x = X; y = Y;}
  16 };
  17
  18 map< point, double > dist;
  19
  20 bool operator ==(const point &a, const point &b){ return (a.x == b.x && a.y == b.y);}
  21 bool operator !=(const point &a, const point &b){ return !(a == b);}
  22 bool operator <(const point &a, const point &b){ return (a.x < b.x || (a.x == b.x && a.y < b.y));}
  23 double distancia(point a, point b){return hypot(a.y-b.y, a.x-b.x);}
  24
  25
  26 struct heapCompare : public binary_function<point, point, bool>
  27 {
  28   bool operator()(const point &x, const point &y) const
  29   { return dist[x] > dist[y]; }
  30 };
  31
  32
  33 struct grafo{
  34   //contiene todos los nodos sueltos
  35   vector<point> nodos;
  36   //contiene un vector con todos los vecinos para el punto point
  37   map< point, vector<point> > vecinos;
  38
  39   void insert(point a){
  40     if (vecinos.count(a) == 1) return; //Ya insertamos este nodo
  41     nodos.push_back(a);
  42     vector<point> v;
  43     vecinos.insert(make_pair(a, v));
  44   }
  45
  46   void make_vecinos(double maxPath){
  47     for (map< point, vector<point> >::iterator it=vecinos.begin(); it!=vecinos.end(); ++it){
  48       if (distancia((*it).first, point(0.00, 0.00)) > maxPath){
  49         continue;
  50       }
  51       for (map< point, vector<point> >::iterator jt = it; jt!=vecinos.end(); ++jt){
  52         if ((*it).first != (*jt).first){
  53           if ((*jt).first.x - (*it).first.x > 1.5){
  54             break;
  55           }
  56           vector<point> adj = vecinos[(*it).first];
  57           if (distancia((*jt).first, (*it).first) <= 1.5){
  58             vecinos[(*it).first].push_back((*jt).first);
  59             vecinos[(*jt).first].push_back((*it).first);
  60           }
  61         }
  62       }
  63     }
  64   }
  65
  66   void initialize(){
  67     dist.clear();
  68     for (int i=0; i<nodos.size(); ++i){
  69       dist[nodos[i]] = infinity;
  70       if (nodos[i].x == 0.00 && nodos[i].y == 0.00){
  71         dist[nodos[i]] = 0.00;
  72       }
  73     }
  74   }
  75
  76   void dijkstra(const double &maxPath, const point &finalPoint){
  77     initialize();
  78
  79     priority_queue<point, vector<point>, heapCompare > q;
  80     q.push(point(0.0, 0.0));
  81     while (!q.empty()){
  82       point u = q.top();
  83       q.pop();
  84       if (distancia(point(0.00, 0.00), u) + distancia(u, finalPoint) <= maxPath){
  85         for (int i=0; i<vecinos[u].size(); ++i){
  86           point v = vecinos[u][i];
  87           if (dist[vecinos[u][i]] > (dist[u] + distancia(u,v))){
  88             dist[vecinos[u][i]] = dist[u] + distancia(u, v);
  89             q.push(v);
  90           }
  91         }
  92       }
  93     }
  94   }
  95
  96 };
  97
  98
  99
 100 int main(){
 101   while (true){
 102
 103     string s;
 104     for (s = ""; s == ""; getline(cin, s));
 105     if (s == "*") break;
 106
 107
 108     grafo g;
 109
 110     stringstream line;
 111     line << s;
 112
 113     int w,h;
 114     line >> w >> h;
 115     g.insert(point((double)w, (double)h));
 116     g.insert(point(0.00, 0.00));
 117     int noPuntos;
 118     cin >> noPuntos;
 119     for (int i=0; i<noPuntos; ++i){
 120       double x,y;
 121       cin >> x >> y;
 122       g.insert(point(x,y));
 123     }
 124
 125
 126     double maximoCamino;
 127     cin >> maximoCamino;
 128
 129     g.make_vecinos(maximoCamino);
 130
 131     g.dijkstra(maximoCamino, point((double)w, (double)h));
 132     if (dist[point((double)w, (double)h)] <= maximoCamino){
 133       printf("I am lucky!\n");
 134     }else{
 135       printf("Boom!\n");
 136     }
 137
 138   }
 139   return 0;
 140 }